package com.c2b.algorithm.leetcode.base;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * <a href='https://leetcode.cn/problems/majority-element-ii/'>多数元素 II(Majority Element II)</a>
 * <p>给定一个大小为 n 的整数数组，找出其中所有出现超过 ⌊ n/3 ⌋ 次的元素。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：nums = [3,2,3]
 *      输出：[3]
 *
 * 示例 2：
 *      输入：nums = [1]
 *      输出：[1]
 *
 * 示例 3：
 *      输入：nums = [1,2]
 *      输出：[1,2]
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>1 <= nums.length <= 5 * 10^4</li>
 *     <li>-10^9 <= nums[i] <= 10^9</li>
 * </ul>
 * </p>
 *
 * <b>进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1)的算法解决此问题。</b>
 *
 * @author c2b
 * @see LC0169MajorityElement_S 多数元素(Majority Element)
 * @see LC0229MajorityElement_II_M 多数元素 II(Majority Element II)
 * @since 2023/12/14 17:14
 */
public class LC0229MajorityElement_II_M {

    static class Solution {

        /**
         * <p>有一个对摩尔投票法非常形象的比喻：多方混战。</p>
         * <p>首先要知道，在任何数组中，出现次数大于该数组长度1/3的值最多只有两个。</p>
         * <p>我们把这道题比作一场多方混战，战斗结果一定只有最多两个阵营幸存，其他阵营被歼灭。数组中的数字即代表某士兵所在的阵营。</p>
         * <p>我们维护两个潜在幸存阵营A和B。我们遍历数组，如果遇到了属于A或者属于B的士兵，则把士兵加入A或B队伍中，该队伍人数加一。继续遍历。</p>
         * <p>
         * 如果遇到了一个士兵既不属于A阵营，也不属于B阵营，这时有两种情况：
         *     <ol>
         *         <li>A阵营和B阵营都还有活着的士兵，那么进行一次厮杀，参与厮杀的三个士兵全部阵亡：A阵营的一个士兵阵亡，B阵营的一个士兵阵亡，这个不知道从哪个阵营来的士兵也阵亡。继续遍历。</li>
         *         <li>A阵营或B阵营已经没有士兵了。这个阵营暂时从地球上消失了。那么把当前遍历到的新士兵算作新的潜在幸存阵营，这个新阵营只有他一个人。继续遍历。</li>
         *     </ol>
         * </p>
         * <p>大战结束，最后A和B阵营就是初始人数最多的阵营。判断一下A，B的人数是否超过所有人数的三分之一就行了。</p>
         */
        public List<Integer> majorityElement(int[] nums) {
            int element1 = 0;
            int vote1 = 0;
            int element2 = 0;
            int vote2 = 0;
            for (int num : nums) {
                if (vote1 > 0 && num == element1) {
                    //如果该元素为第一个元素，则计数加1
                    vote1++;
                } else if (vote2 > 0 && num == element2) {
                    vote2++;
                } else if (vote1 == 0) {
                    // 选择第一个元素
                    element1 = num;
                    vote1++;
                } else if (vote2 == 0) {
                    // 选择第二个元素
                    element2 = num;
                    vote2++;
                } else {
                    //如果三个元素均不相同，则相互抵消1次
                    vote1--;
                    vote2--;
                }
            }
            int cnt1 = 0;
            int cnt2 = 0;
            // 重新确认当前选取的候选人 票数是否超过指定票数。
            for (int num : nums) {
                if (num == element1) {
                    cnt1++;
                } else if (num == element2) {
                    cnt2++;
                }
            }
            // 检测元素出现的次数是否满足要求
            List<Integer> ansList = new ArrayList<>();
            if (cnt1 > nums.length / 3) {
                ansList.add(element1);
            }
            if (cnt2 > nums.length / 3) {
                ansList.add(element2);
            }
            return ansList;
        }

        public List<Integer> majorityElement2(int[] nums) {
            Map<Integer, Integer> cntMap = new HashMap<>();
            for (int num : nums) {
                cntMap.put(num, cntMap.getOrDefault(num, 0) + 1);
            }
            List<Integer> ansList = new ArrayList<>();
            for (Map.Entry<Integer, Integer> entry : cntMap.entrySet()) {
                if (entry.getValue() > nums.length / 3) {
                    ansList.add(entry.getKey());
                }
            }
            return ansList;
        }
    }
}
